#include<vector>
#include<unordered_map>
#include<queue>
using namespace std;
class Solution {
private:
    struct Data {
        int num, weight;
        Data(int num_, int weight_) :num(num_), weight(weight_) {}
    };

    struct Compare {
        bool operator()(const Data& left, const Data& right) {
            if (left.weight < right.weight)
                return true;
            if (left.weight > right.weight)
                return false;
            return left.num < right.num;

        }
    };

    int getWeight(unordered_map<int, int>&weights, int num) {
        if (num == 1) return 0;
        if (weights.find(num) != weights.end())
            return weights[num];
        int res = 1;
        if (num % 2 == 0)
            res += getWeight(weights, num / 2);
        else
            res += getWeight(weights, num * 3 + 1);
        weights[num] = res;
        return res;
    }

    template<typename T, typename Func>
    int findKth(vector<T>&nums, Func& compare,int start,int end,int k) {
        int priv = start;
        int left = start + 1, right = end - 1;
        while (left <= right) {
            while (left <= right && compare(nums[left],nums[priv]))
                ++left;
            while (left <= right && !compare(nums[right], nums[priv]))
                --right;
            if (left <= right)
                swap(nums[left++], nums[right--]);
        }
        swap(nums[right], nums[priv]);
        if (right > k) return findKth(nums, compare, start, right, k);
        if (right < k) return findKth(nums, compare, right +1, end, k);
        return right;
    }

public:
    int getKth(int lo, int hi, int k) {
        unordered_map<int, int> weights;
        vector<Data>dataVec;
        for (int i = lo; i <= hi; ++i) 
            dataVec.emplace_back(i, getWeight(weights, i));
        auto func = Compare();
        int index = findKth(dataVec, func, 0, dataVec.size(), k-1);
        return dataVec[index].num;
    }
};

//int main() {
//    Solution sol;
//    sol.getKth(12, 15, 2);
//}